package top.hkyzf.study.datastructure.linkedlist;

import java.util.Stack;

/**
 * 单链表的实现
 * @author zhufeng
 * @version 1.0
 * @date 2020-12-19 23:44
 */
public class SingleLinkedList {
    // 初始化一个头节点，不存放具体数据，不要更改头节点
    private HeroNode head = new HeroNode(0, "", "");

    // 添加节点
    public void add(HeroNode node) {
        // 由于head节点不可移动，定义一个临时节点
        HeroNode temp = head;
        while (true) {
            // 找到最后了
            if(temp.next == null) {
                break;
            }
            // 没有找到最后则temp后移继续循环
            temp = temp.next;
        }
        // 将新节点添加到链表最后
        temp.next = node;
    }

    // 按照顺序添加节点
    public void addByOrder(HeroNode node) {
        // 由于head节点不可移动，定义一个临时节点
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            // 找到最后了
            if(temp.next == null) {
                break;
            }
            // 没有找到最后，但是下一个节点num大于要添加的节点，则需要在当前节点以及下个节点间添加
            if(temp.next.num > node.num) {
                break;
            // 当前节点的下一个节点num等于要添加的节点，则说明已存在，不可添加
            } else if (temp.next.num == node.num) {
                flag = true;
                break;
            }
            // 没有找到最后则temp后移继续循环
            temp = temp.next;
        }
        // 节点已存在，不可添加
        if(flag) {
            System.out.println("要添加的节点已存在，添加失败，节点num为：" + node.num);
        } else {
            // 将新节点添加到链表最后
            node.next = temp.next;
            temp.next = node;
        }
    }

    // 按照num更新链表某个节点信息
    public void update(HeroNode node) {
        // 先判断链表是否为空
        if(head.next == null) {
            System.out.println("链表为空，不可修改！");
            return;
        }
        // 由于head节点不可移动，定义一个临时节点
        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            // 判断当前节点的num是否跟传过来的num一致
            if(temp.num == node.num) {
                flag = true;
                break;
            }
            // 找到最后了
            if(temp.next == null) {
                System.out.println("没有num为 " + node.num + " 的英雄，修改失败！");
                break;
            }
            // 没有找到最后则temp后移继续循环
            temp = temp.next;
        }
        // 找到了，开始修改
        if(flag) {
            temp.name = node.name;
            temp.nickName = node.nickName;
            System.out.println("修改成功了！");
        }
    }

    // 删除链表中的元素
    public void delete(int num) {
        // 先判断链表是否为空
        if(head.next == null) {
            System.out.println("链表为空，不可删除！");
            return;
        }
        // 由于head节点不可移动，定义一个临时节点
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            // 找到最后了
            if(temp.next == null) {
                System.out.println("没有num为 " + num + " 的英雄，删除失败！");
                break;
            }
            // 判断下一个节点的num是否跟传过来的num一致
            if(temp.next.num == num) {
                flag = true;
                break;
            }
            // 没有找到最后则temp后移继续循环
            temp = temp.next;
        }
        // 找到了，开始删除
        if(flag) {
            temp.next = temp.next.next;
            System.out.println("删除成功了！");
        }
    }

    // 列出链表所有元素
    public void list() {
        // 先判断链表是否为空
        if(head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        // 不为空，开始遍历，由于head节点不可移动，定义一个临时节点
        HeroNode temp = head.next;
        while (true) {
            // 先打印链表当前节点
            System.out.println(temp);
            // 判断下一节点是否为空，为空则遍历完毕，退出循环
            if(temp.next == null) {
                break;
            }
            // 有值则游标后移
            temp = temp.next;
        }
    }

    // 获取单链表中的有效个数
    public int getLength(HeroNode head) {
        int length = 0;
        // 先判断链表是否为空
        if(head.next == null) {
            System.out.println("链表为空！");
            return length;
        }
        // 不为空，开始遍历，由于head节点不可移动，定义一个临时节点
        HeroNode temp = head.next;
        while (true) {
            length++;
            // 判断下一节点是否为空，为空则遍历完毕，退出循环
            if(temp.next == null) {
                break;
            }
            // 有值则游标后移
            temp = temp.next;
        }
        return length;
    }

    // 获取倒数第index个节点（新浪面试题）
    public HeroNode getLastIndexNode(HeroNode head, int index) {
        // 先判断链表是否为空
        if(head.next == null) {
            System.out.println("链表为空！");
            return null;
        }
        int length = getLength(head);
        if(index <= 0 || index > length) {
            System.out.println("输入不合法");
            return null;
        }
        HeroNode temp = head.next;
        for(int i=0; i<(length-index); i++) {
            temp = temp.next;
        }
        return temp;
    }

    // 单链表的反转（腾讯面试题）
    public void revert() {
        // 先判断链表是否为空
        if(head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        // 不为空，开始遍历，由于head节点不可移动，定义一个节点保存当前遍历位置
        HeroNode cur = head.next;
        // 定义新链表的头节点
        HeroNode newHead = new HeroNode(0, "", "");

        while (cur != null) {
            // 旧head指向当前节点的下一节点
            head.next = cur.next;
            // 当前节点的next指向新head的下一个节点
            cur.next = newHead.next;
            // 新head节点指向当前节点
            newHead.next = cur;
            // 当前节点后移
            cur = head.next;
        }
        head.next = newHead.next;
    }

    // 从尾到头打印链表内容（百度面试题）
    // 1.反向遍历法
    public void printFromTailToHead1() {
        // 先判断链表是否为空
        if(head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        this.revert();
        this.list();
    }

    // 2.利用栈实现
    public void printFromTailToHead2() {
        // 先判断链表是否为空
        if(head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode temp = head.next;
        // 入栈
        while(temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        // 遍历输出栈内容
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    // 合并两个有序链表，合并完毕后依然有序（正序）
    public HeroNode merge(HeroNode head1, HeroNode head2) {
        // 先判断链表是否为空
        if(head1.next == null) {
            if(head2.next == null) {
                System.out.println("链表为空！");
                return null;
            } else {
                System.out.println("链表1为空！");
                return head2;

            }
        } else {
            if(head2.next == null) {
                System.out.println("链表2为空！");
                return head1;

            }
        }
        // 两个链表都不为空
        HeroNode temp1 = head1;
        HeroNode cur = head2.next;
        HeroNode temp2 = cur;
        // flag=0未开始，或者循环完毕；flag=1找到了需要插入节点；flag=2找到了一样的，直接跳过
        while (temp2 != null) {
            int flag = 0;
            while (temp1.next != null) {
                // 下一节点大于当前要插入的节点，进行插入
                if(temp2.num < temp1.next.num) {
                    flag = 1;
                    break;

                // 等于直接跳过，不进行插入
                } else if(temp2.num == temp1.next.num) {
                    flag = 2;
                    break;

                // 其他情况继续循环
                } else {
                    temp1 = temp1.next;
                }
            }
            // 没有循环完，跳出循环，找到了准备插入
            if(flag == 1) {
                // 防止进度丢失，先将temp2节点保存
                cur = cur.next;
                // 将节点串到temp1链表上
                temp2.next = temp1.next;
                temp1.next = temp2;
                // temp1游标后移，走到新增的节点
                temp1 = temp1.next;
            // 没有循环玩，跳出循环，找到了一样的数据，不做操作
            } else if(flag == 2) {
                System.out.println("值一样，不进行插入");
                cur = cur.next;
                temp1 = temp1.next;
            // 循环完毕，将链表2剩余节点追加到后面即可
            } else {
                temp1.next = temp2;
                break;
            }
            // 上面保存temp2到cur节点，继续循环temp2链表
            temp2 = cur;
        }
        return head1;
    }

    // 获取head节点
    public HeroNode getHead() {
        return head;
    }
}
